//两两交换链表中的节点
//测试链接 https://leetcode.cn/problems/swap-nodes-in-pairs/
public class SwapPairs {

    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    //方法一：循环 迭代
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null){ //没有或者只有一个结点
            return head;
        }

        ListNode newHead = new ListNode();
        ListNode pre = newHead;
        ListNode cur = head;
        ListNode next = head.next;
        ListNode nnext = next.next;

        while(cur != null && next != null){
            //交换结点
            pre.next = next;
            next.next = cur;
            cur.next = nnext;

            //往后移动，修改指针
            pre = cur; //需注意顺序
            cur = nnext;
            if(nnext != null){
                next = nnext.next;
            }
            if(next != null){
                nnext = next.next;
            }
        }

        return newHead.next;
    }

    //方法二： 递归实现
    public ListNode swapPairs2(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode pre = head;
        ListNode cur = head.next;
        ListNode temp = cur.next;

        cur.next = pre;
        pre.next = swapPairs(temp);
        return cur;
    }
}
